
/**
 * 改为list
 */
public class p1011_3_172ms_34th {

	public static//
	// -----
	// -----
	class Main {
		public static void main(String[] args) throws Exception {
			java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
			while (true) {
				if (Integer.parseInt(reader.readLine()) == 0)
					return;
				String[] parts = reader.readLine().split(" ");
				int[] nums = new int[parts.length];
				for (int i = 0; i < nums.length; i++)
					nums[i] = Integer.parseInt(parts[i]);
				java.util.Arrays.sort(nums);
				System.out.println(process(nums));
			}
		}

		static int process(int[] nums) {
			int sum = 0;
			for (int i : nums)
				sum += i;
			java.util.List<int[]> stat = stat(nums);
			for (width = nums[nums.length - 1]; width <= sum / 2; width++) {
				if (sum % width != 0)
					continue;
				java.util.List<int[]> newStat = shrink(stat);
				if (possible(newStat, newStat.size() - 1, 0, 0))
					return width;
			}
			return sum;
		}

		static java.util.List<int[]> shrink(java.util.List<int[]> old) {
			java.util.List<int[]> stat = new java.util.ArrayList<int[]>();
			int i = 0, j = old.size() - ((old.get(old.size() - 1)[0] == width) ? 2 : 1);
			while (i <= j) {
				int[] item1 = old.get(i), item2 = old.get(j);
				int total = item1[0] + item2[0];
				if (total < width) {
					stat.add(item1);
					i++;
				} else if (total > width) {
					stat.add(item2);
					j--;
				} else {
					int c1 = item1[1], c2 = item2[1];
					if (i == j) {
						if (item1[1] % 2 == 1)
							stat.add(new int[] { item1[0], 1 });
					} else if (c1 > c2)
						stat.add(new int[] { item1[0], c1 - c2 });
					else if (c2 > c1)
						stat.add(new int[] { item2[0], c2 - c1 });
					i++;
					j--;
				}
			}
			return stat;
		}

		static java.util.List<int[]> stat(int[] nums) {
			java.util.List<int[]> stat = new java.util.ArrayList<int[]>();
			int val = nums[0], count = 0;
			for (int v : nums) {
				if (v == val) {
					count++;
				} else {
					stat.add(new int[] { val, count });
					val = v;
					count = 1;
				}
			}
			stat.add(new int[] { val, count });
			return stat;
		}

		static int width;

		static boolean possible(java.util.List<int[]> stats, int maxStat, int left, int maxLeftId) {
			if (left == 0) {
				while (maxStat >= 0 && stats.get(maxStat)[1] == 0)
					maxStat--;
				if (maxStat < 0)
					return true;
				int[] item = stats.get(maxStat);
				item[1]--;
				if (possible(stats, maxStat, width - item[0], maxStat))
					return true;
				item[1]++;
			} else if (left > 0) {
				for (int i = maxLeftId; i >= 0; i--) {
					int[] item = stats.get(i);
					if (item[0] > left || item[1] <= 0)
						continue;
					item[1]--;
					if (possible(stats, maxStat, left - item[0], i))
						return true;
					item[1]++;
				}
			}
			return false;
		}
	}

	// -----
	// -----

	public static void main(String[] args) throws Exception {
		Judge.run();
	}

}
